import java.util.Arrays;

/**
 * 插入排序
 * 以 {2, 6, 12, 10, 11, 16, 4, 7} 为例：
 * 遍历到元素 4 时，发现其小于前一元素 16
 * 则通过 while 循环，将其放置到索引 1 上，即元素 6 之前
 * 而元素 16，12，11，10，6 较大元素，在 while 循环时，都被后移了一个位置
 * 即元素 16 被放置到了原来元素 4 所在的索引 6 上
 */
public class InsertSort {
    public static int[] insertSort(int[] nums) {
        int[] res = Arrays.copyOf(nums, nums.length);
        int len = res.length;
        for (int i = 1; i < len; i++) {
            int cur = res[i];
            int j = i;
            while (j > 0 && cur < res[j - 1]) {
                // 较大的元素依次后移，空出一个位置来放置较小值 temp
                res[j] = res[j - 1];
                j --;
            }
            if (j < i) {
                // 较小值插入到索引 j 上
                res[j] = cur;
            }
        }
        return res;
    }
}
